<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<meta name="generator" content="litedown 0.7">
<title></title>
<style type="text/css">
body {
  font-family: sans-serif;
  max-width: 800px;
  margin: auto;
  padding: 1em;
  line-height: 1.5;
  print-color-adjust: exact;
  -webkit-print-color-adjust: exact;
}
body, .abstract, code, .footnotes, footer, #refs, .caption { font-size: .9em; }
li li { font-size: .95em; }
ul:has(li > input[type="checkbox"]) { list-style: none; padding-left: 1em; }
*, :before, :after { box-sizing: border-box; }
a { color: steelblue; }
pre, img { max-width: 100%; }
pre { white-space: pre-wrap; word-break: break-word; }
pre code { display: block; padding: 1em; overflow-x: auto; }
code { font-family: 'DejaVu Sans Mono', 'Droid Sans Mono', 'Lucida Console', Consolas, Monaco, monospace; }
:not(pre, th) > code, code[class], div > .caption { background: #f8f8f8; }
pre > code:is(:not([class]), .language-plain, .language-none, .plain), .box, .figure, .table { background: inherit; border: 1px solid #eee; }
pre > code {
  &.message { border-color: #9eeaf9; }
  &.warning { background: #fff3cd; border-color: #fff3cd; }
  &.error { background: #f8d7da; border-color: #f8d7da; }
}
.fenced-chunk { border-left: 1px solid #666; }
.code-fence {
  opacity: .4;
  border: 1px dashed #666;
  border-left: 2px solid;
  &:hover { opacity: inherit; }
}
.box, .figure, .table, table { margin: 1em auto; }
div > .caption { padding: 1px 1em; }
.figure { p:has(img, svg), pre:has(svg) { text-align: center; } }
.flex-col { display: flex; justify-content: space-between; }
table {
  &:only-child:not(.table > *) { margin: auto; }
  th, td { padding: 5px; font-variant-numeric: tabular-nums; }
  thead, tfoot, tr:nth-child(even) { background: whitesmoke; }
  thead th { border-bottom: 1px solid #ddd; }
  &:not(.datatable-table) {
    border-top: 1px solid #666;
    border-bottom: 1px solid #666;
  }
}
blockquote {
  color: #666;
  margin: 0;
  padding: 1px 1em;
  border-left: .5em solid #eee;
}
hr, .footnotes::before { border: 1px dashed #ddd; }
.frontmatter { text-align: center; }
#TOC {
  a { text-decoration: none; }
  ul { list-style: none; padding-left: 1em; }
  & > ul { padding: 0; }
  ul ul { border-left: 1px solid lightsteelblue; }
}
.body h2 { border-bottom: 1px solid #666; }
.body .appendix, .appendix ~ h2 { border-bottom-style: dashed; }
.main-number::after { content: "."; }
span[class^="ref-number-"] { font-weight: bold; }
.ref-number-fig::after, .ref-number-tab::after { content: ":"; }
.cross-ref-chp::before { content: "Chapter "; }
.cross-ref-sec::before { content: "Section "; }
.cross-ref-fig::before, .ref-number-fig::before { content: "Figure "; }
.cross-ref-tab::before, .ref-number-tab::before { content: "Table "; }
.cross-ref-eqn::before, .MathJax_ref:has(mjx-mtext > mjx-c + mjx-c)::before { content: "Equation "; }
.abstract, #refs {
  &::before { display: block; margin: 1em auto; font-weight: bold; }
}
.abstract::before { content: "Abstract"; text-align: center; }
#refs::before { content: "Bibliography"; font-size: 1.5em; }
.ref-paren-open::before { content: "("; }
.ref-paren-close::after { content: ")"; }
.ref-semicolon::after { content: "; "; }
.ref-and::after { content: " and "; }
.ref-et-al::after { content: " et al."; font-style: italic; }
.footnote-ref a {
  &::before { content: "["; }
  &::after { content: "]"; }
}
section.footnotes {
  margin-top: 2em;
  &::before { content: ""; display: block; max-width: 20em; }
}
.fade {
  background: repeating-linear-gradient(135deg, white, white 30px, #ddd 32px, #ddd 32px);
  opacity: 0.6;
}

@media print {
  body { max-width: 100%; }
  tr, img { break-inside: avoid; }
}
@media only screen and (min-width: 992px) {
  body:not(.pagesjs) pre:has(.line-numbers):not(:hover) { white-space: pre; }
}
</style>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@xiee/utils@1.14.14/css/prism-xcode.min.css">
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/components/prism-core.min.js" defer></script>
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/plugins/autoloader/prism-autoloader.min.js" defer></script>
</head>
<body>
<div class="frontmatter">
</div>
<div class="body">
<pre><code class="language-r"># Coin Change Problem
#
# The Coin Change problem finds the minimum number of coins needed to make a certain amount
# using a given set of coin denominations.
#
# Time Complexity: O(amount * n) where n = number of coin denominations
# Space Complexity: O(amount)
#
# Applications:
# - Currency and cash management
# - Making change in vending machines or payment systems
# - Dynamic resource allocation
# - Minimum cost problems in algorithms

# Function to compute minimum coins required
coin_change &lt;- function(coins, amount) {
  #' Compute minimum number of coins needed to make the given amount
  #' @param coins: Numeric vector of coin denominations
  #' @param amount: Total amount to make
  #' @return: Minimum number of coins required, or -1 if not possible
  
  # Initialize DP array
  dp &lt;- rep(Inf, amount + 1)
  dp[0 + 1] &lt;- 0  # zero coins needed for amount 0
  
  for (i in 1:amount) {
    for (coin in coins) {
      if (coin &lt;= i) {
        dp[i + 1] &lt;- min(dp[i + 1], 1 + dp[i - coin + 1])
      }
    }
  }
  
  if (dp[amount + 1] == Inf) {
    return(-1)
  } else {
    return(dp[amount + 1])
  }
}

# Function to print the DP table (for educational purposes)
print_coin_change_dp &lt;- function(dp, amount) {
  cat(&quot;DP Table for Coin Change:\n&quot;)
  for (i in 0:amount) {
    cat(sprintf(&quot;Amount %2d: %s\n&quot;, i, dp[i + 1]))
  }
  cat(&quot;\n&quot;)
}


# Example Usage &amp; Testing
cat(&quot;=== Coin Change Problem ===\n\n&quot;)
</code></pre>
<pre><code>## === Coin Change Problem ===
</code></pre>
<pre><code class="language-r"># Test 1: Basic Example
coins &lt;- c(1, 2, 5)
amount &lt;- 11
cat(&quot;Coins:&quot;, paste(coins, collapse = &quot;, &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Coins: 1, 2, 5
</code></pre>
<pre><code class="language-r">cat(&quot;Amount:&quot;, amount, &quot;\n&quot;)
</code></pre>
<pre><code>## Amount: 11
</code></pre>
<pre><code class="language-r">min_coins &lt;- coin_change(coins, amount)
cat(&quot;Minimum Coins Needed:&quot;, min_coins, &quot;\n\n&quot;)
</code></pre>
<pre><code>## Minimum Coins Needed: 3
</code></pre>
<pre><code class="language-r"># Test 2: No solution case
coins &lt;- c(2, 4)
amount &lt;- 7
cat(&quot;Coins:&quot;, paste(coins, collapse = &quot;, &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Coins: 2, 4
</code></pre>
<pre><code class="language-r">cat(&quot;Amount:&quot;, amount, &quot;\n&quot;)
</code></pre>
<pre><code>## Amount: 7
</code></pre>
<pre><code class="language-r">min_coins &lt;- coin_change(coins, amount)
cat(&quot;Minimum Coins Needed:&quot;, min_coins, &quot;\n\n&quot;)
</code></pre>
<pre><code>## Minimum Coins Needed: -1
</code></pre>
<pre><code class="language-r"># Test 3: Larger dataset
coins &lt;- c(1, 3, 4, 5)
amount &lt;- 7
cat(&quot;Coins:&quot;, paste(coins, collapse = &quot;, &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Coins: 1, 3, 4, 5
</code></pre>
<pre><code class="language-r">cat(&quot;Amount:&quot;, amount, &quot;\n&quot;)
</code></pre>
<pre><code>## Amount: 7
</code></pre>
<pre><code class="language-r">min_coins &lt;- coin_change(coins, amount)
cat(&quot;Minimum Coins Needed:&quot;, min_coins, &quot;\n\n&quot;)
</code></pre>
<pre><code>## Minimum Coins Needed: 2
</code></pre>
</div>
</body>
</html>
